package problem91_Decode_Ways;

public class Solution {
	public int numDecodings(String s) {
		s="00"+s;
		int[] dp=new int[s.length()];
		char[] input=s.toCharArray();
		dp[0]=0;dp[1]=1;
		for(int i=2;i<input.length;i++){
			int tmp=(input[i-1]-'0')*10+(input[i]-'0');
			dp[i]=(input[i]!='0'?dp[i-1]:0)+(tmp>=10&&tmp<=26?dp[i-2]:0);
		}
		return s.length()==2?0:dp[s.length()-1];
    }
	
	public static void main(String[] args){
		System.out.println(new Solution().numDecodings("13"));
	}
}
